(1) Field of the Invention
The present invention relates to a method for solving optimization problems, particularly minimal Hamiltonian cycle type problems, and a practical utilization of the solutions for these problems, including the application of the solutions to routing as employed in naval convoying or other transit point scheduling.
(2) Description of the Prior Art
It is known in the art that a “Traveling Salesman Problem” (TSP) involves finding a minimum length Hamiltonian Cycle (HC)—the path of visiting each vertex once and returning to the starting vertex. The minimum length HC resolves the routing problem of the TSP which can also be applied to naval convoying, trucks routes or even transit point scheduling such satellite positioning.
The symmetric TSP with N vertices has (N−1)!/2 permutations, precluding an exhaustive search except for small N. Even a relatively small problem (e.g., N=20) has 1016 distinct HCs; N=40 leads to 1046 distinct HCs. The Euclidean TSP is classified as an NP-hard problem, having no known algorithm for the general case whose number of operations is a polynomial function of N.
The (N−1)!/2 permutations assume that any vertex can occupy any of N positions. Isolating vertices into spatial zones locks each into a limited range of positions, subject to boundary vertex permutations. This falls into a general area of dynamic programming.
Partitioning the vertices into sub-problems has been done for the Euclidean TSP. In particular, a Polynomial Time Approximation Scheme (PTAS) generates a tour exceeding the optimal length by no more than a factor of 1+ε in time N0(1/ε). The approach involves a bounding square box dissected into squares and shifted randomly, with restrictions on edge crossings (to specified portals).
Most prior work on the TSP has focused on heuristics that generate tours. For example: a simple heuristic involves going to the nearest point. More complex heuristics include genetic algorithms, simulated annealing, and neural nets. In some cases, these approaches have found optimal tours. More likely, the approaches will come close (often to within two percent) of the optimal tour.
Another approach to the TSP makes use of a “DNA Computer”. This approach involves DNA strands (with appropriate genetic coding to represent each point) mixed together in a test tube. A 7-point problem was solved by chemically eliminating all non-solutions. Although this process avoids exhausting every possible permutation creating during the chemical reactions, the process may take several days to find a solution.
Practical applications connected with the TSP go beyond traditional combinatorial problems involving scheduling and routing (e.g., planning of supply convoy routes to support naval bases). In physics, a three-dimensional Ising model used for studying phase transitions can be translated into a TSP problem. Scattering of X-rays from crystals can potentially involve accounting for as many as 30,000 different radiation paths. Other applications include VLSI chip fabrication, protein structure prediction, and the assignment of frequencies to transmitters in a communications network. Existing patent references disclose methods for solving the TSP:
In Marks et al. (U.S. Pat. No. 6,826,549), a system is provided that enables an interactively guided heuristic search for solving a combinatorial optimization problem. The system initially performs a hill-climbing search of the combinatorial optimization problem to obtain a solution using initial default parameters. The current solution and the combinatorial optimization problem are visualized on an optimization table, a table-top display device. The parameters are altered based on the visualization of the combinatorial optimization problem and the current solution. Then, the searching, visualizing, and setting are repeated until the solution is selected as an acceptable solution of the combinatorial optimization problem. During the repeating, the parameters can be a set of probabilities, and in which case the search is a random perturbation-based search. Alternatively, the parameters can be a set of priorities, in which case the search is an exhaustive local search.
In Okano (U.S. Pat. No. 6,510,384), a method is provided for increasing the execution speed of a cost-minimizing routing algorithm, as employed in trucking or job shop scheduling. Penalty functions for succeeding transit points along a route are added and examined for validity during trial route evaluation. A soft time window is set for each transit point and proposed routes are evaluated using a total cost including all soft time windows along the route and the length of the route. A static soft time window function and a dynamic soft time window function are correlated with each transit point. The dynamic soft time window function for each transit point is the sum of the static soft time window function for the transit point and the dynamic soft time window function for a succeeding transit point in the direction of travel.
In Goray et. Al. (U.S. Pat. No. 6,636,840), a computer system and associated method is configured to support solving NP-complete problems such as minimal Hamiltonian cycle type problems. A primary network represented by the matrix of its edges is recorded in the memory space and an equivalent representation of the primary network is formed as a set of subnetworks. Nodes of a present path are reordered according to a set of reordering rules and edge weights of edges of the set of subnetworks are changed according to a set of edge weight changing rules.